import math
from util import *
import random
import numpy as np
import pickle
from Method.GA_for_init_ms_deploy import GA_algorithm

class GSMS:
    #没有服务删除和部署的过程，一开始就进行初始化部署，然后后续不进行改变。
    def __init__(self, cloud_system):
        self.cloud_system=cloud_system
        self.env=cloud_system.env
        
        self.ms_obj_to_end_time={}
        self.next_remove_ms=None
        self.remove_process=None
        return
    
    def init_deploy(self):
        
        if self.cloud_system.args.elastic_deploy==False:
            #不弹性部署，则每类微服务部署一个，后续不进行微服务部署
            system_ms_kind_list=self.cloud_system.ms_kind_list
            for ms_kind in system_ms_kind_list:
                self.schedule_deploy_one_ms(ms_kind, None, without_cold_start=True)
                
            assert len(system_ms_kind_list)==len(self.ms_obj_to_end_time.keys())
            
    def schedule_deploy_one_ms(self, ms_kind, aim_node, without_cold_start=False):
        #获取冷启动时间
        if without_cold_start==True:
            cold_start_time=0
        else:
            cold_start_time=self.cloud_system.get_cold_start_time(ms_kind)
            
        if aim_node!=None:
            flage, ms_obj=aim_node.deploy_ms(ms_kind,without_cold_start=without_cold_start)
        else:
            flage=False
            
        if flage==True:
            #初始化的时候设置为冷启动结束时间
            self.set_ms_obj_end_time(ms_obj, cold_start_time)
            return ms_obj
        else:
            node_num=self.cloud_system.args.bare_metal_node_num
            node_index_list=random.sample(range(node_num), node_num)
            for node_index in node_index_list:
                node=self.cloud_system.bare_metal_node_list[node_index]
                flage, ms_obj =node.deploy_ms(ms_kind, without_cold_start=without_cold_start)
                if flage==True:
                    #初始化的时候设置为冷启动结束时间
                    self.set_ms_obj_end_time(ms_obj, cold_start_time)
                    return ms_obj
        
        print(f"schedule_random_deploy error (capacity lack)!")
        exit(-1)
    
    
    
#************************************************************************************************************    
    #调度入口函数
    def do_schedule_deploy(self):
        not_scheduled_tasks=[]
        for task in self.cloud_system.pending_task_queue:
            base_request=self.cloud_system.service_to_callgraph_dict[task.request.service_name]
            self.schedule_GSMS_get_replica(base_request, task.request.deadline)
            replica_num=base_request.task_id_to_replica_num[task.task_id]
            task.set_replica_num(replica_num)
            sub_deadline=base_request.task_id_to_sub_deadline[task.task_id]
            result=self.schedule_GSMS_deploy_and_select_ms(task, sub_deadline, replica_num, base_request.task_id_to_obj[task.task_id])
            #说明调度失败
            if result==False:
                not_scheduled_tasks.append(task)
        #清空队列
        self.cloud_system.pending_task_queue=not_scheduled_tasks
        if self.cloud_system.args.elastic_deploy==True:
            self.reset_ms_remove_event()
        
        
        return
    
        
    def schedule_GSMS_get_replica(self, request_base, deadline):
        
        if len(request_base.task_id_to_replica_num.keys())==0:
             
            #对base request 中的所有task都进行处理，得到uprank,和sub_deadline
            self.schedule_GSMS_get_upward_rank(request_base)
            
            all_task_num=len(request_base.task_id_list)
            # all_task_num=request_base.max_task_num_per_call
            request_reliability=self.cloud_system.service_to_reliability[request_base.service_name]
            single_up_relia=math.pow(request_reliability, 1/all_task_num)
            all_ready_num=0
            all_ready_reliability=1
            waiting_deal_task_list=[]
            #寻找最底部的task
            for task in request_base.task_id_to_obj.values():
                waiting_deal_task_list.append(task)
            waiting_deal_task_list.sort(key=lambda x:x.uprank, reverse=True)
            for task_t in waiting_deal_task_list:
                #获取当前task需要的可靠性大小
                this_req=request_reliability/(all_ready_reliability*math.pow(single_up_relia, all_task_num-all_ready_num-1))
                #获取指定微服务故障参数
                ms_lambda=self.cloud_system.ms_kind_to_transient_lambda[task_t.ms_kind]
                #获取单个task无故障概率
                single_reliability=get_reliability_without_failure(task_t.ave_deal_time,ms_lambda)
                #获取副本数量
                replica_num=get_aim_replica_num(this_req, single_reliability)
                request_base.task_id_to_replica_num[task_t.task_id]=replica_num      
                
                #更新和存储副本信息，可靠性信息
                all_ready_reliability=all_ready_reliability*(1-math.pow(1-single_reliability, replica_num))
                all_ready_num+=1
                
        self.schedule_GSMS_get_sub_deadline(request_base, deadline)
        return
    
    #计算uprank 
    def schedule_GSMS_get_upward_rank(self, request_base):
        waiting_deal_task_list=[]
        dealed_task_list=[]
        ms_record_for_task={} #task_id to ms_obj
        for task in request_base.task_id_to_obj.values():
            #首先找到最低端的task
            if len(task.sub_task_list)==0:
                waiting_deal_task_list.append(task)
                
        while len(waiting_deal_task_list)>0:
            task_t=waiting_deal_task_list.pop(0) 
            if len(task_t.sub_task_list)==0 or list_is_sub_of_another_list(task_t.sub_task_list,dealed_task_list):
                ms_obj_list=self.cloud_system.get_available_ms_obj_with_ms_kind(task_t.ms_kind)
                if len(ms_obj_list)==0:
                    aim_ms_obj=None
                else:
                    #这里选择微服务主要是为了计算通信时间TT
                    aim_ms_obj=self.cloud_system.rng_general.choice(ms_obj_list)
                ET=task_t.ave_deal_time
                max_succ_uprank=0
                for succ_task in task_t.sub_task_list:
                    if succ_task.task_id in ms_record_for_task.keys():
                        succ_task_ms_obj=ms_record_for_task[succ_task.task_id]
                    else:
                        succ_task_ms_obj=None
                    #原始方法是针对异构机器，找处理能力最快的机器，这里进行调整，由于本文中都是同构机器，如果有一方没有存在的微服务，则TT=0
                    TT=self.cloud_system.get_TT_time(succ_task, succ_task_ms_obj, aim_ms_obj, base_flage=True)
                    succ_uprank=succ_task.uprank
                    max_succ_uprank=max(max_succ_uprank, TT+succ_uprank)
                task_t.uprank=max_succ_uprank+ET
                dealed_task_list.append(task_t)
                ms_record_for_task[task_t.task_id]=aim_ms_obj
                if task_t.parent_task != None and task_t.parent_task not in waiting_deal_task_list:
                    waiting_deal_task_list.append(task_t.parent_task)
            else:
                waiting_deal_task_list.append(task_t)          
        return
    
    #基于uprank 计算每个task的sub deadline 
    def schedule_GSMS_get_sub_deadline(self, request_base, deadline):
        uprank_entry=max(request_base.start_task_list, key=lambda x:x.uprank).uprank
        # deadline=self.cloud_system.service_to_deadline[request_base.service_name]
        for task in request_base.task_id_to_obj.values():
            if uprank_entry==0:
                task.sub_deadline=deadline
            else:
                task.sub_deadline=deadline*(uprank_entry-task.uprank+task.ave_deal_time)/uprank_entry
                
            request_base.task_id_to_sub_deadline[task.task_id]=task.sub_deadline
        return
    
    #为task选择微服务或者部署新的微服务
    def schedule_GSMS_deploy_and_select_ms(self, task, sub_deadline, replica_num, task_base):
        #获取现在的时间
        
        time_now=self.cloud_system.env.now
        task.ave_deal_time=task_base.ave_deal_time
        #获取所有正在运行的微服务列表
        ms_obj_list=self.cloud_system.get_available_ms_obj_with_ms_kind(task.ms_kind)
        #获取每个微服务队列信息，并升序排序
        ##统计每个类型的微服务队列长度信息
        ms_obj_with_early_start_time_list=[]
        for ms_obj in ms_obj_list:
            #更新最早开始时间
            ms_idle_time=self.update_ms_obj_end_time(ms_obj)   #都是绝对时间
            TT=self.cloud_system.get_TT_time(task, ms_obj, task.first_parent_ms_obj)
            early_start_time=max(time_now+TT, ms_idle_time)
            ms_obj_with_early_start_time_list.append([early_start_time, ms_obj])
        
        ##调度到微服务上
        for index in range(replica_num):
            if self.cloud_system.args.elastic_deploy==True and self.judge_need_new_ms(task, task_base, sub_deadline, ms_obj_with_early_start_time_list):
                #部署新的微服务并调度task过去
                ms_obj_new=self.schedule_GSMS_random_deploy(task.ms_kind)
                #需要排除无法部署的情况
                if ms_obj_new==None:
                    if index == 0:   #刚开始部署就失败，则调度失败，直接返回
                        return False
                    else:
                        #说明已经部署过至少一次了，可以重复放到同一个MS上
                        assert len(ms_obj_with_early_start_time_list)>0
                        [early_start_time, ms_obj_new]=ms_obj_with_early_start_time_list[0]
                        
                TT_new=self.cloud_system.get_TT_time(task, ms_obj_new, task.first_parent_ms_obj)
                early_start_time_new=max(time_now+TT_new, self.ms_obj_to_end_time[ms_obj_new])
                self.set_ms_obj_end_time(ms_obj_new, early_start_time_new+task_base.ave_deal_time)
                self.cloud_system.env.process(ms_obj_new.put_task_to_queue_event(task))
                #这里面存的应该是下一个任务的最早开始时间，需要加上TT传输时间
                ms_obj_with_early_start_time_list.append([early_start_time_new+task_base.ave_deal_time, ms_obj_new])
                task.aim_ms_obj_list.append(ms_obj_new)
                continue
                
            ms_obj_with_early_start_time_list.sort(key=lambda x:x[0])
            [early_start_time, aim_ms]=ms_obj_with_early_start_time_list[0]
            plan_end_time=early_start_time+task_base.ave_deal_time
            #如果最早获取的ms都无法满足subdeadline需求，则重新创建一个(重新创建一个有冷启动时间)
            # TT_new=self.cloud_system.get_TT_time(task, aim_ms, task.first_parent_ms_obj)
            self.set_ms_obj_end_time(aim_ms, plan_end_time)
            self.cloud_system.env.process(aim_ms.put_task_to_queue_event(task)) 
            ms_obj_with_early_start_time_list[0][0]+=task_base.ave_deal_time
            task.aim_ms_obj_list.append(aim_ms)
        return True
    
    #计算平均传输时间TT
    # def schedule_GSMS_get_average_TT(self, task, ms_obj):
    #     TT=0
    #     if task.parent_task!=None:
    #         #处理父task有多个副本的情况，传输时间取平均值
    #         for parent_ms_obj in task.parent_task.aim_ms_obj_list:
    #             TT+=self.cloud_system.get_TT_time(task, ms_obj, parent_ms_obj)
    #         TT=TT/len(task.parent_task.aim_ms_obj_list)
    #     return TT
    
    #随机部署
    def schedule_GSMS_random_deploy(self, ms_kind):
        
        
        node_num=self.cloud_system.args.bare_metal_node_num
        node_index_list=random.sample(range(node_num), node_num)
        for node_index in node_index_list:
            node=self.cloud_system.bare_metal_node_list[node_index]
            # msid_list=node.msid_to_msobj.keys()
            # for ms_id in msid_list:
                # if node.msid_to_msobj[ms_id].ms_kind!=ms_kind and node.msid_to_msobj[ms_id].can_be_rm():
                #     node.remove_ms(ms_id)
            flage, ms_obj =node.deploy_ms(ms_kind)
            if flage==False:
                continue
            # assert flage==True
            #初始化的时候设置为冷启动结束时间
            self.set_ms_obj_end_time(ms_obj, self.env.now+self.cloud_system.get_cold_start_time(ms_kind))
            return ms_obj
        
        return None
        
    
    def judge_need_new_ms(self, task, task_base, sub_deadline, ms_obj_with_early_start_time_list):
        #需要新建 True， 不需要为False
        if len(ms_obj_with_early_start_time_list)==0:
            return True
        ms_obj_with_early_start_time_list.sort(key=lambda x:x[0])
        [early_start_time, aim_ms]=ms_obj_with_early_start_time_list[0]
        plan_end_time=early_start_time+task_base.ave_deal_time
        #如果最早获取的ms都无法满足subdeadline需求,且新建的最早开始时间小于当前的最早开始时间，则重新创建一个(重新创建一个有冷启动时间)
        if plan_end_time>sub_deadline+task.request.arrive_time and early_start_time>self.env.now+self.cloud_system.get_cold_start_time(aim_ms.ms_kind):
            return True
        else:
            return False
        
        
    def set_ms_obj_end_time(self, ms_obj, end_time):
        self.ms_obj_to_end_time[ms_obj]=end_time
        return
    def update_ms_obj_end_time(self, ms_obj):
        estimate_end_time=ms_obj.get_estimate_end_time()
        self.ms_obj_to_end_time[ms_obj]=estimate_end_time
        return estimate_end_time
        
    def get_ms_obj_end_time(self, ms_obj):
        return self.ms_obj_to_end_time[ms_obj]
    
    
    def reset_ms_remove_event(self):
        try:
            self.remove_process.interrupt()
        except:
            pass
            
        if len(self.ms_obj_to_end_time.keys())>0:
            sorted_keys=sorted(self.ms_obj_to_end_time, key=lambda k:self.ms_obj_to_end_time[k])
            #寻找第一个非常驻微服务
            self.next_remove_ms=None
            for index in range(len(sorted_keys)):
                if sorted_keys[index].stable_flage_for_ours==False:
                    self.next_remove_ms=sorted_keys[index]
                    break
            if self.next_remove_ms==None:
                return
            else:
                interval=max(0, self.ms_obj_to_end_time[self.next_remove_ms]-self.cloud_system.env.now)
                self.remove_process=self.cloud_system.env.process(self.remove_latest_end_ms_obj(interval))
        
    def remove_latest_end_ms_obj(self, interval):
        try:
            yield self.cloud_system.env.timeout(interval)
            #先删除之前确定的需要删除的微服务
            if self.next_remove_ms !=None:
                if self.next_remove_ms.can_be_rm():
                    self.next_remove_ms.node_obj.remove_ms(self.next_remove_ms.ms_id)
                    del self.ms_obj_to_end_time[self.next_remove_ms]
                else:
                    self.ms_obj_to_end_time[self.next_remove_ms]+=100
            
            if len(self.ms_obj_to_end_time.keys())>0:
                sorted_keys=sorted(self.ms_obj_to_end_time, key=lambda k:self.ms_obj_to_end_time[k])
                self.next_remove_ms=None
                for index in range(len(sorted_keys)):
                    if sorted_keys[index].stable_flage_for_ours==False:
                        self.next_remove_ms=sorted_keys[index]
                        break
                if self.next_remove_ms==None:
                    return
                else:
                    interval=max(0, self.ms_obj_to_end_time[self.next_remove_ms]-self.cloud_system.env.now)
                    self.remove_process=self.cloud_system.env.process(self.remove_latest_end_ms_obj(interval))
            else:
                self.remove_process=None
        except:
            pass
        return
        
    #这是被立即执行删除的动作，由微服务本身触发
    def ms_complete_and_can_be_rm(self, ms_obj):
        del self.ms_obj_to_end_time[ms_obj]
        ms_obj.node_obj.remove_ms(ms_obj.ms_id)
        
        if self.next_remove_ms.ms_id==ms_obj.ms_id:
            self.reset_ms_remove_event()
        
        
        
        
        
    # def schedule_GSMS_is_all_sub_task_with_replica(self, task_t, task_id_to_ms_list_dict):
    #     for sub_task in task_t.sub_task_list:
    #         if sub_task.task_id not in task_id_to_ms_list_dict.keys():
    #             return False
    #     return True
        